import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree implements IList{
    public int Treesize;
    //    获取树中结点的个数,那就是遍历一边即可
    @Override
    public int size(BTNode root) {
//        这里随便选一种
        if(root==null){
            return 0;
        }
        Treesize+=1;
        size(root.left);
        size(root.right);
        return Treesize;
    }
//    还有一种写法,子问题的方法 那树的总的结点个数就等于左子树的结点个数+右子树的结点个数+1
    public int size2(BTNode root){
        if(root==null){
            return 0;
        }
        int temp1=size2(root.left);
        int temp2=size2(root.right);
        return temp1+temp2+1;
    }

//获取叶子节点的数量
    @Override
    public int getLeafNodeCount(BTNode root) {
//        那这棵树的叶子节点的个数就是左子树的叶子节点+右子树的叶子结点
        if(root==null){
            return 0;
        }
//        判断叶子结点
        if(root.left==null&&root.right==null){
            return 1;
        }
        int temp1=getLeafNodeCount(root.left);
        int temp2=getLeafNodeCount(root.right);
        return temp1+temp2;
    }
//第k层的结点数量
    int kcount;
    @Override
    public int getKLevelNodeCount(BTNode root,int k) {
//        k层的结点数=左子树的k-1层结点数+右子树的k-1层结点数
//        每一层减一,k=1时,这一层的结点数就是k层的结点数.
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }
//获取树的高度
    @Override
    public int getHeight(BTNode root) {
//        书的高度等于左子树,右子树的高度较高的高度加1
//        如果判断树到底了呢?左右子树都为空
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return Math.max(getHeight(root.left),getHeight(root.right))+1;

    }
    public int getHight2(BTNode root) {
        if (root == null) {
            return 0;
        }
            int leftHeight = getHight2(root.left);
            int rightHeight = getHight2(root.right);
            return Math.max(leftHeight, rightHeight) + 1;

    }
//    遍历即可
    @Override
    public BTNode find(BTNode root, int val) {
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        if(find(root.left,val)!=null){
            return find(root.left,val);
        }else if(find(root.right,val)!=null){
            return find(root.right,val);
        }else{
            return null;
        }
    }
//层序遍历
    @Override
    public void levleOrder(BTNode root) {
//       队列可以很好的表示
        if(root==null){
            return;
        }
        Queue<BTNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            BTNode temp = queue.poll();
            System.out.println(temp.val);
            if (temp.left != null) {
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
        }
    }
//判断一棵树是不是完全二叉树

    @Override
    public boolean isCompleteTree(BTNode root) {
        if(root==null){
            return true;
        }
        Queue<BTNode> btNodes=new LinkedList<>();
        btNodes.add(root);
        while(!btNodes.isEmpty()){
            BTNode temp=btNodes.poll();
            if(temp!=null){
                btNodes.add(temp.left);
                btNodes.add(temp.right);
            }else{
                break;
            }
        }
        while(!btNodes.isEmpty()){
            BTNode btNode=btNodes.poll();
            if(btNode!=null){
                return false;
            }
        }
        return true;
    }

    //    先创建一个节点
    public static class BTNode{
        public BTNode left;
        public BTNode right;
        public int val;
        //    给结点写一个构造方法
        public BTNode(int val){
            this.val=val;
        }
    }
    public BTNode root;
    //    先创建一个树,为了方便操作
    public BTNode createBinaryTree(){
        BTNode node1=new BTNode(1);
        BTNode node2=new BTNode(2);
        BTNode node3=new BTNode(3);
        BTNode node4=new BTNode(4);
        BTNode node5=new BTNode(5);
        BTNode node6=new BTNode(6);
        BTNode node7=new BTNode(7);
        BTNode node8=new BTNode(8);
        root=node1;
        node1.left=node2;
        node1.right=node3;
        node3.left=node4;
        node4.right=node5;
        node5.left=node6;
        node5.right=node7;
        node3.right=node8;
        return root;
    }
    //    接着写二叉树的三种遍历方式
//    1.前序遍历
    public void preOrder(BTNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //    中序遍历
    public void inOrder(BTNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);

    }
    //    后序遍历
    public void postOrder(BTNode root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }






}